from typing import *
from math import inf


class Solution:

    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        mxs = [[-inf] * n for _ in range(n)]  # [l,r]范围上的最大值
        for r in range(n):
            mxs[r][r] = arr[r]
            for l in range(r - 1, -1, -1):
                mxs[l][r] = max(mxs[l + 1][r], arr[l])
        dp = [[inf] * n for _ in range(n)]  # [l,r] 范围上按照题意产生的最小值
        for r in range(n):  # 右界
            dp[r][r] = 0
            for l in range(r - 1, -1, -1):  # 左界
                for k in range(l, r):  # 枚举左右子树分割点，k左子树的最右点
                    dp[l][r] = min(
                        dp[l][r],
                        dp[l][k] + dp[k + 1][r] + mxs[l][k] * mxs[k + 1][r])
        return dp[0][n - 1]


class Solution:

    def mctFromLeafValues(self, arr: List[int]) -> int:
        n = len(arr)
        mxs = [[-inf] * n for _ in range(n)]  # [l,r]范围上的最大值
        dp = [[inf] * n for _ in range(n)]  # [l,r] 范围上按照题意产生的最小值
        for r in range(n):  # 右界
            dp[r][r] = 0
            mxs[r][r] = arr[r]
            for l in range(r - 1, -1, -1):  # 左界
                mxs[l][r] = max(mxs[l + 1][r], arr[l])
                for k in range(l, r):  # 枚举左右子树分割点，k左子树的最右点
                    dp[l][r] = min(
                        dp[l][r],
                        dp[l][k] + dp[k + 1][r] + mxs[l][k] * mxs[k + 1][r])
        return dp[0][n - 1]


so = Solution()
print(so.mctFromLeafValues(arr=[6, 2, 4]))
print(so.mctFromLeafValues(arr=[4, 11]))
